package com.zhang.tree;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhang
 * @time 2022/03/10 08:23:27
 */
public class Tree {
    private class Node {
        private int value;
        private Node leftChild;
        private Node rightChild;

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node=" + value;
        }
    }

    private Node root;


    public void insert(int value) {
        Node node = new Node(value);

        if (root == null) {
            root = node;
            return;
        }

        Node current = root;
        while (true) {
            if (value < current.value) {
                if (current.leftChild == null) {
                    current.leftChild = node;
                    break;
                }
                current = current.leftChild;
            } else {
                if (current.rightChild == null) {
                    current.rightChild = node;
                    break;
                }
                current = current.rightChild;
            }
        }
    }

    public boolean find(int value) {
        Node current = root;
        while (current != null) {
            if (value < current.value) {
                current = current.leftChild;
            } else if (value > current.value) {
                current = current.rightChild;
            } else {
                return true;
            }

        }
        return false;
    }
    public void traversePreOrder() {
        traversePreOrder(root);
    }

    private void traversePreOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.value);
        traversePreOrder(root.leftChild);
        traversePreOrder(root.rightChild);

    }
    public void traverseInOrder() {
        traverseInOrder(root);
    }

    private void traverseInOrder(Node root) {
        if (root == null) {
            return;
        }
        traverseInOrder(root.leftChild);
        System.out.println(root.value);
        traverseInOrder(root.rightChild);

    }
    public void traversePostOrder() {
        traversePostOrder(root);
    }

    private void traversePostOrder(Node root) {
        if (root == null) {
            return;
        }
        traversePostOrder(root.leftChild);

        traversePostOrder(root.rightChild);
        System.out.println(root.value);

    }

    public int height() {
        return height(root);
    }

    private int height(Node root) {
        if (root == null) {
            return -1;
        }
        if (isLeaf(root)) {
            return 0;
        }
        return 1 + Math.max(height(root.leftChild), height(root.rightChild));

    }

    public int min() {
        if (root == null) {
            throw new IllegalStateException();
        }
        Node current = root;
        Node last = current;
        while (current != null) {
            last = current;
            current = last.leftChild;
        }
        return last.value;
    }

    private int min(Node root) {
        if (isLeaf(root)) {
            return root.value;
        }

        int left = min(root.leftChild);
        int right = min(root.rightChild);

        return Math.min(Math.min(left, right), root.value);
    }
    public boolean equals(Tree other) {
        if (other == null) {
            return false;
        }

        return equals(root, other.root);
    }

    private boolean equals(Node first, Node second) {
        if (first == null && second == null) {
            return true;
        }

        if (first != null && second != null) {
            return first.value == second.value
                    && equals(first.leftChild, second.leftChild)
                    && equals(first.leftChild, second.leftChild);
        }
        return false;
    }

    public boolean isBinarySerarchTree() {
        return isBinarySerarchTree(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    private boolean isBinarySerarchTree(Node root, int minValue, int maxValue) {
        if (root == null) {
            return false;
        }
        if (root.value < minValue || root.value > maxValue) {
            return false;
        }
        return
                isBinarySerarchTree(root.leftChild, minValue, root.value - 1)
                        && isBinarySerarchTree(root.rightChild, root.value + 1, maxValue);
    }



    private boolean isLeaf(Node node) {
        return node.leftChild == null && node.rightChild == null;
    }

    public ArrayList<Node> getNodesAtDistance(int distance) {
        ArrayList<Node> list = new ArrayList<>();
        getNodesAtDistance(root, distance, list);
        return list;
    }

    private void getNodesAtDistance(Node root, int distance, ArrayList<Node> list) {
        if (root == null) {
            return;
        }
        if (distance == 0) {
            list.add(root);
            return;
        }
        getNodesAtDistance(root.leftChild,distance-1,list);
        getNodesAtDistance(root.rightChild, distance - 1, list);

    }

    public void traverseLevelOrder() {
        for (int i = 0; i <= height() ; i++) {
            getNodesAtDistance(i).forEach(System.out::println);
        }

    }

    public int size() {
        return size(root);
    }

    private int size(Node root) {
        if (root == null) {
            return 0;
        }
        if (isLeaf(root)) {
            return 1;
        }

        return 1 + size(root.leftChild) + size(root.rightChild);
    }

    public int countLeaves() {
        return countLeaves(root);
    }

    private int countLeaves(Node root) {
        if (root == null) {
            return 0;
        }
        if (isLeaf(root)) {
            return 1;
        }
        return countLeaves(root.leftChild) + countLeaves(root.rightChild);
    }

    public int max() {
        return max(root);
    }

    private int max(Node root) {
        if (root.rightChild == null) {
            return root.value;
        }
        return max(root.rightChild);
    }

    public boolean contains(int value) {
        return contains(root, value);
    }

    private boolean contains(Node root, int value) {
        if (root == null) {
            return false;
        }
        if (root.value == value) {
            return true;
        }
        return contains(root.leftChild, value) || contains(root.rightChild, value);
    }

    public boolean areSibling(int first, int second) {
        return areSibling(first, second, root);
    }

    private boolean areSibling(int first, int second, Node root) {
        if (root == null) {
            return false;
        }
        boolean areSibling = false;
        if (root.leftChild != null && root.rightChild != null) {
            areSibling = (root.leftChild.value == first && root.rightChild.value == second) ||
                    (root.rightChild.value == first && root.leftChild.value == second);
        }
        return areSibling || areSibling(first, second, root.leftChild)
                || areSibling(first, second, root.rightChild);


    }

    public List<Integer> getAncestor(int value) {
        List<Integer> list = new ArrayList<>();
        getAncestor(root, value, list);
        return list;
    }

    private boolean getAncestor(Node root, int value, List<Integer> list) {

        if (root == null) {
            return false;
        }
        if (root.value == value) {
            return true;
        }
        if (getAncestor(root.leftChild, value, list) ||
                getAncestor(root.rightChild, value, list)) {
            list.add(root.value);
            return true;
        }
        return false;

    }

    public boolean isBalanced() {
        return isBalanced(root);
    }

    private boolean isBalanced(Node root) {
        if (root == null) {
            return true;
        }

        int balanceFactor = height(root.leftChild) - height(root.leftChild);

        return Math.abs(balanceFactor) <= 1 &&
                isBalanced(root.leftChild) &&
                isBalanced(root.rightChild);

    }


    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.insert(6);
        tree.insert(9);
        tree.insert(5);
        tree.insert(12);
        tree.insert(10);
        tree.insert(4);
        tree.insert(1);
        System.out.println(tree.getAncestor(1));

    }

}
